package com.fengdi.book.easy;

import com.fengdi.publicObject.ListNode;

import java.util.ArrayList;
import java.util.Stack;

public class LinkListSolution {

    public static class DeleteNode {

        public void deleteNode(ListNode node) {
            if(node == null) return;
            ListNode next = node.next;
            while (next != null) {
                node.val = next.val;
                if(next.next == null) {
                    node.next = null;
                }else {
                    node = next;
                    next = next.next;
                }
            }
        }
    }

    public static class RemoveNthFromEnd {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            if(head == null) return null;

            ListNode fast = head;
            ListNode slow = head;

            for(int i = 0; i <= n; i++) {
                if(fast == null) {
                    head = head.next;
                    return head;
                }
                fast = fast.next;
            }

            while(fast != null) {
                fast = fast.next;
                slow = slow.next;
            }

            slow.next = slow.next.next;

            return head;
        }
    }

    public static class ReverseList {
        public ListNode reverseList(ListNode head) {
            if(head == null || head.next == null) return head;

            Stack<ListNode> stack = new Stack<>();
            ListNode cur = head;

            while(cur != null) {
                stack.push(cur);
                cur = cur.next;
            }
            cur = stack.pop();
            head = cur;
            cur.next = null;

            while(!stack.isEmpty()) {
                cur.next = stack.pop();
                cur = cur.next;
                cur.next = null;
            }

            return head;
        }
    }

    public static class MergeTwoLists {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if(l1 == null) return l2;
            if(l2 == null) return l1;

            ListNode head = new ListNode();
            ListNode cur = head;
            ListNode h1 = l1, h2 = l2;

            while(h1 != null && h2 != null) {
                if(h1.val <= h2.val) {
                    cur.next = h1;
                    h1 = h1.next;
                }else {
                    cur.next = h2;
                    h2 = h2.next;
                }
                cur = cur.next;
            }

            if(h1 != null) cur.next = h1;
            if(h2 != null) cur.next = h2;

            return head.next;
        }
    }

    public static class IsPalindrome {
        public boolean isPalindrome(ListNode head) {
            ListNode fast = head, slow = head;
            //通过快慢指针找到中点
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            //如果fast不为空，说明链表的长度是奇数个
            if (fast != null) {
                slow = slow.next;
            }
            //反转后半部分链表
            slow = reverse(slow);

            fast = head;
            while (slow != null) {
                //然后比较，判断节点值是否相等
                if (fast.val != slow.val)
                    return false;
                fast = fast.next;
                slow = slow.next;
            }
            return true;
        }

        //反转链表
        public ListNode reverse(ListNode head) {
            ListNode prev = null;
            while (head != null) {
                ListNode next = head.next;
                head.next = prev;
                prev = head;
                head = next;
            }
            return prev;
        }
    }

    public static class HasCycle {
        public boolean hasCycle(ListNode head) {
            if(head == null) return false;
            if(head.next == null) return false;

            ListNode fast = head.next, slow = head;

            while(fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if(slow == fast) return true;
            }

            return false;
        }
    }
}
